/*
 * @lc app=leetcode.cn id=139 lang=cpp
 *
 * [139] 单词拆分
 */

// @lc code=start
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    vector<vector<bool>> dp;
    size_t min_len, max_len;
    set<string> dict;

    bool findPath(int end_pos)
    {
        if(!dp[end_pos][0]) return false;
        if(end_pos == 0) return true;
        for(int i = min_len; i <= max_len && i <= end_pos; i++)
        {
            if(dp[end_pos][i] && dp[end_pos-i][0] && findPath(end_pos - i))  return true;
        }
        return false;
    }

    bool wordBreak(string s, vector<string> &wordDict)
    {

        min_len = wordDict[0].length();
        max_len = min_len;
        for (auto &it : wordDict)
        {
            dict.insert(it);
            min_len = min(it.length(), min_len);
            max_len = max(it.length(), max_len);
        }

        dp = vector<vector<bool>>(s.length() + 1, vector<bool>(max_len + 1, 0));
        dp[0][0] = true;


        for (int i = 0; i <= s.length() - min_len; i++)
        {
            if(dp[i][0])
                for (int j = min_len; j <= max_len && j <= s.length() - i; j++)
                {
                    dp[i+j][j] = dict.find(s.substr(i, j)) != dict.end();
                    if(dp[i+j][j]) dp[i+j][0] = true;
                }
        }

        return findPath(s.length());
    }
};

// int main()
// {
//     string s = "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa";
//     vector<string> v = {"a","aa","aaa","aaaa","aaaaa","aaaaaa","aaaaaaa","aaaaaaaa","aaaaaaaaa","aaaaaaaaaa"};
//     bool ans = Solution().wordBreak(s, v);
//     cout << ans << endl;
//     return 0;
// }
// @lc code=end
